package com.zj.learn.offer;

import com.alibaba.fastjson.JSON;
import org.apache.commons.lang3.text.StrBuilder;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 电子科大穆春林-剑指Offer Java代码
 *
 * @author xi.yang
 * @create 2019-06-10 9:34
 **/
public class SwordReferToJavaOffer {
    /**
     * 1.给定一个已排序（从左到右递增，从上到下递增）二维数组和一个整数，寻找数组中是否存在该整数
     * 思路：从左下或右上角开始搜索
     * @param arr 给定数组，这里其实是矩阵
     * @param target 查找数
     * @return 是否存在
     */
    private static boolean findTargetBySortArr(int[][] arr, int target) {
        int row = arr.length - 1;
        int col = 0;
        while (row >= 0 && col < arr[row].length) {
            int cur = arr[row][col];
            if (cur > target) {
                row--;
            } else if (cur < target) {
                col++;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 2.字符串替换
     * @param str 给定字符串
     * @return 替换后字符串
     */
    private static String replaceSpace(String str) {
        return str.replaceAll(" ", "%d");
    }

    /**
     * 3.从尾到头打印链表
     * @param listNode 链表
     * @return 输出顺序
     */
    private static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.value);
            listNode = listNode.next;
        }
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (!stack.isEmpty()) {
            arrayList.add(stack.pop());
        }
        return arrayList;
    }

    /**
     * 寻找一个从小到大排列的数组的旋转数组中的最小值
     * [5,6,7,1,2,3,4]为[1,2,3,4,5,6,7]的旋转数组
     * @param array 给定数组
     * @return 最小值
     */
    private static int minNumberInRotateArray(int[] array) {
        if (array == null) {
            return 0;
        }
        if (array.length == 1) {
            return array[0];
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i + 1] < array[i]) {
                return array[i + 1];
            }
        }
        return array[0];
    }

    /**
     * 递归法算斐波拉契数列
     * @param n 第几个值
     * @return 值
     */
    private static int fibonacciSequence1(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fibonacciSequence1(n - 1) + fibonacciSequence1(n - 2);
    }

    /**
     * 循环计算斐波拉契数列
     * @param n 第几个值
     * @return 值
     */
    private static int fibonacciSequence2(int n) {
        int f0 = 0, f1 = 1;
        if (0 == n) {
            return f0;
        }
        if (1 == n) {
            return f1;
        }
        int fn = 0;
        for (int i = 2; i <= n; i++) {
            fn = f0 + f1;
            f0 = f1;
            f1 = fn;
        }
        return fn;
    }

    /**
     * TODO 搞懂通项公式
     * 利用数学中斐波拉契数列通项公式
     * @param n 第几个值
     * @return 值
     */
    private static int fibonacciSequence3(int n) {
        BigDecimal bigDecimal5 = new BigDecimal(5.0);
        BigDecimal bigDecimal1 = new BigDecimal(1.0);
        BigDecimal bigDecimal2 = new BigDecimal(2.0);
        // 5^(1/2)
        BigDecimal bigDecimal = new BigDecimal(Math.pow(bigDecimal5.doubleValue(), bigDecimal1.doubleValue() / 2));
        return bigDecimal1.add(bigDecimal).divide(bigDecimal2, RoundingMode.HALF_UP).pow(n)
                .subtract(bigDecimal1.subtract(bigDecimal).divide(bigDecimal2, RoundingMode.HALF_UP).pow(n))
                .divide(bigDecimal, RoundingMode.HALF_UP).intValue();
    }

    /**
     * 求一个整数转换成二进制后1的个数
     * 转换成char数组比较
     * @param n 给定整数
     * @return 1的个数
     */
    private static int numberOfOne1(int n) {
        int count = 0;
        char[] chars = Integer.toBinaryString(n).toCharArray();
        for (char aChar : chars) {
            if ('1' == aChar) {
                count++;
            }
        }
        return count;
    }

    /**
     * 求一个整数转换成二进制后1的个数
     * 位运算求解
     * @param n 给定整数
     * @return 二进制1的个数
     */
    private static int numberOfOne2(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }

    /**
     * 求一个整数转换成二进制后1的个数
     * 利用"1"进行与运算判断
     * 把"1"左移而不是把n右移是因为右移的话负数会死循环
     * @param n 给定整数
     * @return 二进制1的个数
     */
    private static int numberOfOne3(int n) {
        int count = 0;
        int flag = 1;
        while (flag != 0) {
            if ((flag & n) != 0) {
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }

    /**
     * 求一个数的exponent次方
     * @param base 基数
     * @param exponent 次方
     * @return 运算结果
     */
    private static double power(double base, int exponent) {
        return Math.pow(base, exponent);
    }

    /**
     * 将数组奇数排前办部分，偶数排后半部分，并且保证奇数和奇数、偶数和偶数的相对位置不变
     *
     * @param array 给定数组
     */
    private static void reOrderArray(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        int i = 0, j;
        while (i < array.length) {
            // 找第一个偶数
            while (i < array.length && !isEven(array[i])) {
                i++;
            }
            j = i + 1;
            // 找偶数后面的第一个基数
            while (j < array.length && isEven(array[j])) {
                j++;
            }
            if (j < array.length) {
                int tmp = array[j];
                if (j - i >= 0) System.arraycopy(array, i, array, i + 1, j - i);
                array[i++] = tmp;
            } else {
                // 查找失败跳出
                break;
            }
        }
    }

    /**
     * 判断一个数是否是偶数
     *
     * @param num 给定数是否是偶数
     * @return 判断结果
     */
    private static boolean isEven(int num) {
        return (num & 1) != 1;
    }

    /**
     * 重建二叉树
     *
     * @param pre 前序遍历结果
     * @param in  中序遍历结果
     * @return
     */
    private static TreeNode reBuildTree(int[] pre, int[] in) {
        TreeNode treeNode = reBuildTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        return treeNode;
    }

    /**
     * 迭代重建二叉树
     * @param pre 前序遍历二叉树数组
     * @param startPre 前序开始
     * @param endPre 前序结束
     * @param in 中序遍历二叉树数组
     * @param startIn 中序开始
     * @param endIn 中序结束
     * @return 重建后的二叉树
     */
    private static TreeNode reBuildTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (startPre > endPre || startIn > endIn) {
            return null;
        }
        // 构造根节点
        TreeNode root = new TreeNode(pre[startPre]);
        for (int i = startIn; i <= endIn; i++) {
            if (in[i] == pre[startPre]) {
                root.left = reBuildTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                root.right = reBuildTree(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
                break;
            }
        }
        return root;
    }

    /**
     * 寻找一个链表的倒数第k个节点
     * @param listNode
     * @param k
     * @return
     */
    public static ListNode findKthToTail(ListNode listNode, int k) {
        if (null == listNode || k <= 0) {
            return null;
        }
        ListNode tail = listNode;
        for (int i = 1; i < k; i++) {
            if (tail.next != null) {
                tail = tail.next;
            } else {
                // k超过了范围
                return null;
            }
        }
        while (tail.next != null) {
            tail = tail.next;
            listNode = listNode.next;
        }
        return listNode;
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public static ListNode reverseListNode(ListNode head) {
        if (null == head) {
            return null;
        }
        ListNode p = head.next;
        ListNode temp = p;
        ListNode q = head;
        q.next = null;
        while (p != null) {
            temp.next = p.next;
            p.next = q;
            q = p;
            p = temp;
        }
        return q;
    }

    /**
     * 测试用
     * @param args app args
     */
    public static void main(String[] args) {
        System.out.println("1.数组查找");
        int[][] arr = {
                {0, 1, 2, 3},
                {4, 11, 12, 13},
                {15, 16, 18, 19},
                {20, 21, 22, 23}
        };
        int target = 13;
        System.out.println(findTargetBySortArr(arr, target));

        System.out.println("2.字符串替换");
        String str = "hello you guys";
        System.out.println(replaceSpace(str));

        System.out.println("3.从尾到头打印链表");
        System.out.println(printListFromTailToHead(new ListNode(1, 2, 3, 4, 5, 6)));

        // TODO: 2019/6/10 4.重建二叉树
        System.out.println("4.重建二叉树");
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode treeNode = reBuildTree(pre, in);
        System.out.println(treeNode);

        System.out.println("5.用两个栈实现队列");
        Stack2Queue stack2Queue = new Stack2Queue();
        stack2Queue.push(1);
        stack2Queue.push(2);
        stack2Queue.push(3);
        stack2Queue.push(4);
        stack2Queue.push(5);
        while (!stack2Queue.isEmpty()) {
            System.out.println(stack2Queue.pop());
        }

        System.out.println("6.找出旋转数组的最小数");
        System.out.println(minNumberInRotateArray(new int[]{5, 6, 7, 1, 2, 3, 4}));

        System.out.println("7.斐波拉契数列");
        int n = 10;
        System.out.println(fibonacciSequence1(n) + "===" + fibonacciSequence2(n) + "===" + fibonacciSequence3(n));

        // TODO: 2019/6/10
        System.out.println("8.青蛙跳台阶");

        System.out.println("11.二进制中1的个数");
        System.out.println(numberOfOne1(n) + "===" + numberOfOne2(n) + "===" + numberOfOne3(n));

        System.out.println("14.求一个数的n次方");
        double base = 12.5D;
        int exponent = 3;
        System.out.println(power(base, exponent));

        System.out.println("15.调整数组顺序");
        int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        reOrderArray(array);
        System.out.println(Arrays.toString(array));

        System.out.println("16.链表中倒数第k个节点");
        System.out.println(findKthToTail(new ListNode(1, 2, 5, 9, 8, 10, 6, 3, 2, 4, 6), 6));

        System.out.println("17.反转链表");
        System.out.println(reverseListNode(new ListNode(1, 2, 3, 4, 5, 6, 7, 8, 9)));
    }
}

/**
 * 链表
 */
class ListNode{
    ListNode(Integer... values) {
        if (null == values || values.length == 0) {
            return;
        }
        this.value = values[0];
        if (values.length > 1) {
            List<Integer> list = new ArrayList<>(Arrays.asList(values));
            list.remove(0);
            this.next = new ListNode(list.toArray(new Integer[list.size() - 1]));
        }
    }

    Integer value;
    ListNode next;

    @Override
    public String toString() {
        List<Integer> array = new ArrayList<>();
        array.add(value);
        ListNode temp = next;
        while (temp != null) {
            array.add(temp.value);
            temp = temp.next;
        }
        return JSON.toJSONString(array);
    }
}

/**
 * 用两个栈实现队列
 * 栈是先进后出，用两个栈就可以实现队列的先进先出
 */
class Stack2Queue{
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();
    void push(Integer item) {
        stack2.push(item);
    }

    Integer pop() {
        if (stack1.isEmpty()) {
            while (!stack2.isEmpty()) {
                stack1.push(stack2.pop());
            }
        }
        return stack1.pop();
    }

    boolean isEmpty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}